"""P16 16.基础提升 普通递归、记忆化搜索、严格表结构"""

"""
存在N个正整数，一个机器人需要从S位置走到E位置，k表示可以移动的步数，
求可以有多少种走法
"""


def walk_ways1(n: int, e: int, k: int, cur: int) -> int:
    """普通递归实现思路，时间复杂度O(2 ** k)"""
    if k == 0:
        return 1 if cur == e else 0
    if cur == 1:
        return walk_ways1(n, e, k - 1, 2)
    if cur == n:
        return walk_ways1(n, e, k - 1, n - 1)
    return walk_ways1(n, e, k - 1, cur - 1) + walk_ways1(n, e, k - 1, cur + 1)


"""如果递归中的动态参数固定后的返回结果相同，可以做无后效性的修改"""


def walk_ways2(n: int, e: int, k: int, cur: int, d=None) -> int:
    """记忆化搜索思路，时间复杂度O(N * k)"""
    if d is None:
        d = dict()
    if (k, cur) in d:
        return d.get((k, cur))
    if k == 0:
        d[(k, cur)] = 1 if cur == e else 0
        return d.get((k, cur))
    if cur == 1:
        d[(k, cur)] = walk_ways2(n, e, k - 1, 2, d)
    elif cur == n:
        d[(k, cur)] = walk_ways2(n, e, k - 1, n - 1, d)
    else:
        d[(k, cur)] = walk_ways2(n, e, k - 1, cur - 1, d) + \
                      walk_ways2(n, e, k - 1, cur + 1, d)
    return d.get((k, cur))


"""
严格表结构的动态规划纠结于位置依赖的顺序

严格表结构分析过程：
1、根据可变参数的数量和范围来定义表的可变维度和大小
2、标出要计算的终止位置
3、根据base case标出不用计算直接出答案的位置
4、推理出普通位置如何依赖其他位置的
5、根据2,3,4的条件，确认依次计算的顺序
"""


def walk_ways3(n: int, e: int, k: int, s: int) -> int:
    """严格表结构思路，时间复杂度O(N * k)"""
    walk_map = list()
    row = list()

    for i in range(n):
        if i + 1 == e:
            row.append(1)
        else:
            row.append(0)
    walk_map.append(row)

    for i in range(k):
        row = list()
        for j in range(n):
            if j == 0:
                row.append(walk_map[-1][1])
            elif j == n - 1:
                row.append(walk_map[-1][n - 2])
            else:
                row.append(walk_map[-1][j - 1] + walk_map[-1][j + 1])
        walk_map.append(row)

    return walk_map[-1][s - 1]
